The present invention relates to the field of editing compressed images. More specifically, in one embodiment the invention provides means for editing portions of compressed images without decompressing the entire image.
Modern color imagery for cameras and scanners requires huge amounts of memory to store image files containing a data representation of the input or scanned image. A typical image such as that used with a color copier with 8.5".times.11" (216 mm.times.297 mm) paper, a resolution of 400 dots per inch (15.75 per mm), and 3 bytes (24 bits) to represent the color for each dot, would occupy 44.88 megabytes of memory. In addition to the size of the memory, the memory must have high bandwidth for real time applications, such as a color copier where 15 pages per minute is a typical demand. This implies a bandwidth, or data rate, of almost 90 megabits/second. Both these requirements drive up the cost of imaging systems. Compression techniques have been used to solve both the bandwidth and the storage problems for quite a while. With compression, an image file can be stored in less memory, and the image can be moved across any bandwidth-limited channel faster since fewer bits are used to represent the image. Compression involves passing the raw image data into a compressor, which combines and analyzes the patterns in the raw data to produce a compressed image file where the original image is not readily discernable without a corresponding decompression.
If an image is to be edited, scaled, rotated, or otherwise processed, random access to any or all of the pixels is required. Once the processing is complete, the edits must be saved to the image file to update the pixels in that image. If the image file being processed is compressed, the conventional means for obtaining random pixel access is to decompress the entire image into a frame store, perform the processing, and then recompress the image into a new image file. The problem with this is that no memory is saved by decompressing, since memory is needed for the frame store. The bandwidth is also lowered, since compression and decompression of entire images takes time. This additional processing time and memory is often wasted, since even the most expensive display in an imaging system could not display the entire image at full resolution.
Compression methods for compressing image data are known. One such compression standard is JPEG (Joint Photographic Experts Group). Other standards include JBIG, Fax G3 or G4, and GIF. In JPEG, to give one example, an image is represented by a two-dimensional array of picture elements, or pixels. If the image is grayscale, each pixel is represented by an intensity value, and if the image is color, the image is divided into several component images (such as red, green and blue components for an image separated according to the RGB color separation standard), with each pixel of each component image represented by a component color value.
Before image data (referred to herein as an image file, which contains the data from an image) is compressed into a compressed image file, the image is divided into components (unless the image is monochrome, in which case there is only one component) and then each component is divided into blocks each covering an image area of a square of eight by eight, or 64, pixels. Within each block, the 64 pixels are transformed, using a discrete cosine transform, into 64 frequency-like basis function amplitudes, where one is a DC value and the other 63 are AC values. These values are then encoded into compressed image data.
To achieve high compression, a difference between the DC value of a block and the DC value of a preceding block is used in place of the absolute DC value of the block. Given that in most images, fewer bits are needed to represent the differential values than the absolute values, higher overall compression ratios of the image data can be obtained. For this reason, many image compression schemes other than JPEG use similar techniques for compression and the use of differential values.
Subsampling of color is often used to increase the compressibility of an image. Where an image is separated into the three components of the YUV (Y, C.sub.r, C.sub.b) color space, the Y component represents luminance (Y), the U, or C.sub.r, component represents the red minus green chrominance, and the V, or C.sub.b, component represents the blue minus green chrominance. Visually, the luminance component is the most important components and the resolution of the other two components can often be reduced without introducing undesirable artifacts into an image. This reduction of color resolution relative to luminance resolution is known as subsampling. Reducing the resolution of each color component (U and V) by half is referred to as 2:1:1 subsampling, since for each two luminance (Y) pixel color values, only one pair of (U,V) pixel color values are provided. Without subsampling (1:1:1), a one-pixel area is described by a total of three pixels (1 L, 1 U, 1 V), whereas with 2:1:1 subsampling, a two-pixel area is described by a total of four pixels (2 L, 1 U, 1 V), resulting in a reduction of the image data file size by a third. With 4:1:1 subsampling, a four-pixel area is covered by six pixels rather than twelve, resulting in a reduction of image data file size by a half. When subsampling is used, the blocks of different color components span different sized areas, so to keep the component blocks together, all the blocks for a small area are kept together when coding and decoding. For example, with 2:1:1 subsampling, four blocks, a U block, a V block, and two Y blocks are needed to cover an area of 8 pixels by 16 pixels, so those four blocks are kept together. With 4:1:1 subsampling, a region of 16 pixels by 16 pixels is covered by six blocks (4 Y, 1 U, 1 V), which are kept together. This smallest unit of compressible and decompressable data is known as a "minimum coded unit" or "MCU". According to the JPEG standard, data can be extracted from a compressed image file one MCU at a time.
The process of compression involves transforming each of the 64 pixel color values associated with a block into a differential DC value and 63 AC values, grouping blocks together into MCUs for multi-block MCUs, and then reducing the number of bits needed to describe each MCU through entropy encoding. The compressed MCUs which make up a compressed image are then tagged with identifying information, such as the MCU's location within the image when uncompressed, length data to indicate how many bits are contained in the MCU and the like, and the MCUs are stored sequentially as a compressed image file. Length data is needed since the MCUs are variable length, the length being a function of the data being compressed and the type of compression used. The process of entropy encoding is generally referred to as coding, while compressing refers to the process of blocking, cosine transforming and coding image data.
Significantly, differential DC values for blocks of an image can be extracted from a compressed image after the step of entropy decoding the image data, which is less effort than completely decompressing the image which, for one, requires the additional step of inverse cosine transforming the data. Because a block need not be inverse transformed to obtain its DC value, the effort required to obtain the DC value is much less than that of obtaining the decompressed block, since cosine transforms and inverse transforms are very computationally intense operations.
To decompress an image, each MCU from an image file is decompressed into one or more image blocks by the reverse operations of those operations used to compress the data. Entropy decoding is applied to a compressed MCU, and the result is a differential DC value and 63 AC values for each block. Next, the differential DC values are converted to absolute DC values by adding the absolute DC value of the block to the left of the block of interest. Of course, for this DC value regeneration process to work, all the blocks to the left of the block of interest must be processed. Next, the blocks are passed through an inverse cosine transform, to result in the uncompressed pixel color value data.
While differential encoding of slowly changing values from block to block, such as the DC value, increases the compression, it increases the difficulty of decompressing less than all of an image, since decompression of some blocks in the partial image will require reference to blocks which are not in the partial image.
Further difficulties arise in partial decompression when the partial image is edited and recompressed, since the degree of compression depends on the orderliness of the image data, and therefore MCUs will change size as the image portion which they represent changes. Consequently, simply replacing the MCUs from the partial image with the MCUs from the edited partial image is impractical, unless the entire image is decompressed, edited and recompressed.
From the above it is seen that an improved method for manipulating and editing compressed images is needed.